{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #查找总价格为目标值的两个商品"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: twoSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #查找总价格为目标值的两个商品"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>购物车内的商品价格按照升序记录于数组 <code>price</code>。请在购物车中找到两个商品的价格总和刚好是 <code>target</code>。若存在多种情况，返回任一结果即可。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>price = [3, 9, 12, 15], target = 18\n",
    "<strong>输出：</strong>[3,15] 或者 [15,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>price = [8, 21, 27, 34, 52, 66], target = 61\n",
    "<strong>输出：</strong>[27,34] 或者 [34,27]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= price.length &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= price[i] &lt;= 10^6</code></li>\n",
    "\t<li><code>1 &lt;= target &lt;= 2*10^6</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [he-wei-sde-liang-ge-shu-zi-lcof](https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [he-wei-sde-liang-ge-shu-zi-lcof](https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3, 9, 12, 15]\\n18', '[8, 21, 27, 34, 52, 66]\\n61']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        p1, p2 = 0, len(price) - 1\n",
    "        while p1 < p2:\n",
    "            if price[p1] + price[p2] == target:\n",
    "                return [price[p1], price[p2]]\n",
    "            elif price[p1] + price[p2] > target:\n",
    "                p2 -= 1\n",
    "            else:\n",
    "                p1 += 1\n",
    "        return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        d = {}\n",
    "        for num in nums:\n",
    "            if target - num in d:\n",
    "                return [num, target - num]\n",
    "            else:\n",
    "                d[num] = 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        li = set()\n",
    "        for i in nums:\n",
    "            if i in li:\n",
    "                return [i, target-i]\n",
    "            li.add(target-i)\n",
    "        return []\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "\n",
    "        hashset = set()\n",
    "\n",
    "        for n in nums:\n",
    "\n",
    "            if target - n in hashset:\n",
    "\n",
    "                return n,target - n\n",
    "\n",
    "            hashset.add(n)\n",
    "\n",
    "        return None\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        left = 0\n",
    "        right = len(nums)\n",
    "        # 定义搜索区间：左闭右开\n",
    "        while left + 1 <= right:\n",
    "            if nums[left] + nums[right-1] == target:\n",
    "                return nums[left], nums[right-1]\n",
    "\n",
    "            elif nums[left] + nums[right-1] < target:\n",
    "                left += 1\n",
    "\n",
    "            elif nums[left] + nums[right-1] > target:\n",
    "                right -= 1\n",
    "        \n",
    "        return None\n",
    "\n",
    "    def find(self, nums, left, right, target):\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        num_dict = dict()\n",
    "        i, j = 0, len(nums) - 1\n",
    "        while i < j:\n",
    "            num_dict[nums[i]] = nums[i]\n",
    "            num_dict[nums[j]] = nums[j]\n",
    "            if nums[i] != target - nums[i]:ti = target - nums[i] \n",
    "            if nums[j] != target - nums[j]:tj = target - nums[j]\n",
    "            if ti in num_dict.keys():\n",
    "                return [nums[i], num_dict[ti]]\n",
    "            elif tj in num_dict.keys():\n",
    "                return [nums[j], num_dict[tj]]\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        l, r = 0, len(price) - 1\n",
    "        while l < r:\n",
    "            sum_price = price[l] + price[r]\n",
    "            if sum_price == target:\n",
    "                return [price[l], price[r]]\n",
    "            elif sum_price < target:\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        # binary + two pointer\n",
    "        start, end = 0, len(price) - 1\n",
    "        while start < end: \n",
    "            if price[start] + price[end] == target: \n",
    "                return [price[start], price[end]]\n",
    "            elif price[start] + price[end] < target: \n",
    "                start += 1\n",
    "            else: \n",
    "                end -= 1\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        start = 0\n",
    "        end = len(price) - 1\n",
    "        while start <= end:\n",
    "        #     mid = (start + end) // 2\n",
    "        #     if price[mid] > target:\n",
    "        #         end = mid - 1\n",
    "            if price[start] + price[end] == target:\n",
    "                return [price[start], price[end]]\n",
    "            elif price[start] + price[end] < target:\n",
    "                start += 1\n",
    "            else:\n",
    "                end -= 1\n",
    "            \n",
    "        else:\n",
    "            return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        i, j = 0, len(price) - 1\n",
    "        while i < j:\n",
    "            if price[i] + price[j] == target:\n",
    "                return [price[i], price[j]]\n",
    "            elif price[i] + price[j] < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        x=0\n",
    "        y=len(price)-1\n",
    "        for i in range(len(price)-1):\n",
    "            print(price[x]+price[y])\n",
    "            if price[x]+price[y]>target:\n",
    "                y-=1                \n",
    "            elif price[x]+price[y]<target:\n",
    "                x+=1\n",
    "            else:\n",
    "                return [price[x],price[y]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        x=0\n",
    "        y=len(price)-1\n",
    "        for i in range(len(price)-1):\n",
    "            if price[x]+price[y]>target:\n",
    "                y-=1                \n",
    "            elif price[x]+price[y]<target:\n",
    "                x+=1\n",
    "            else:\n",
    "                return [price[x],price[y]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        i, j = 0, len(price)-1\n",
    "        while i<=j:\n",
    "            s = price[i]+price[j]\n",
    "            if s > target:\n",
    "                j -= 1\n",
    "            elif s < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                return [price[i], price[j]]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        i,j=0,len(price)-1\n",
    "        while i<j:\n",
    "            if price[i]+price[j]>target: j-=1\n",
    "            elif price[i]+price[j]<target:i+=1\n",
    "            else: return [price[i],price[j]]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for idx in range(n):\n",
    "            rest = target - nums[idx]\n",
    "            left, right = idx, n - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums[mid] == rest:\n",
    "                    return [nums[idx], nums[mid]]\n",
    "                elif nums[mid] > rest:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        i, j = 0, len(price) - 1\n",
    "        while i < j:\n",
    "            s = price[i] + price[j]\n",
    "            if s > target: j -= 1\n",
    "            elif s < target: i += 1\n",
    "            else: return price[i], price[j]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "\n",
    "        i = 0\n",
    "        j = len(price) - 1\n",
    "        while i < j:\n",
    "            if (price[i] +  price[j]) == target:\n",
    "                return [price[i], price[j]]\n",
    "            elif (price[i] +  price[j]) < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return []\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        left, right = 0, len(price) - 1\n",
    "        while left < right:\n",
    "            if price[left] + price[right] == target:\n",
    "                return [price[left], price[right]]\n",
    "            elif price[left] + price[right] > target:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        i,j=0,len(price)-1\n",
    "        while True:\n",
    "            while price[i]+price[j]>target:\n",
    "                j-=1\n",
    "            while price[i]+price[j]<target:\n",
    "                i+=1\n",
    "            if price[i]+price[j]==target:\n",
    "                return [price[i],price[j]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        left, right = 0, len(price) - 1\n",
    "        while left < right:\n",
    "            if price[left] + price[right] == target:\n",
    "                return [price[left], price[right]]\n",
    "            elif price[left] + price[right] > target:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "\n",
    "\n",
    "        targetSubPrice = []\n",
    "        for i in range(len(price)):\n",
    "            targetSubPrice.append(target - price[i])\n",
    "\n",
    "\n",
    "        i = 0\n",
    "        j = len(price) - 1\n",
    "        while i < j:\n",
    "            if price[i] == targetSubPrice[j]:\n",
    "                return [price[i], price[j]]\n",
    "            elif price[i] < targetSubPrice[j]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return []\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        max_count = target - nums[0]\n",
    "        # for x in nums[::-1]:\n",
    "        #     if x > max_count: nums.pop()\n",
    "        for x in range(len(nums)-1, 0, -1):\n",
    "            if nums[x] <= max_count: break\n",
    "        nums = nums[:(x+1)]\n",
    "        \n",
    "        i, j = 0, len(nums) - 1\n",
    "        while i < j:\n",
    "            s = nums[i] + nums[j]\n",
    "            if s > target: j -= 1\n",
    "            elif s < target: i += 1\n",
    "            else: return nums[i], nums[j]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        num2idx = {}\n",
    "        for idx, num in enumerate(nums):\n",
    "            if num not in num2idx:\n",
    "                num2idx[target-num] = idx\n",
    "            else:\n",
    "                return [nums[num2idx[num]], num]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        dic = dict()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in dic:\n",
    "                dic[target-nums[i]] = i\n",
    "            else:\n",
    "                return nums[dic[nums[i]]], nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        hash_ = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in hash_:\n",
    "                return [nums[i], nums[hash_[nums[i]]]]\n",
    "            else:\n",
    "                hash_[target-nums[i]] = i\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        # 递增排序数组，所以可以直接用双指针法\n",
    "        # left = 0\n",
    "        # right = len(nums) - 1\n",
    "        # while left < right:\n",
    "        #     if nums[left] + nums[right] > target:\n",
    "        #         right -= 1\n",
    "        #     elif nums[left] + nums[right] < target:\n",
    "        #         left += 1\n",
    "        #     else:\n",
    "        #         return [nums[left], nums[right]]\n",
    "        # return []\n",
    "\n",
    "        # 哈希表\n",
    "        dic = {}\n",
    "        for i, x in enumerate(nums):\n",
    "            y = target - x\n",
    "            if x in dic:\n",
    "                return [nums[dic[x]], nums[i]]\n",
    "            else:\n",
    "                dic[y] = i\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        bucket = collections.defaultdict(int)\n",
    "        for i in range(len(nums)):\n",
    "            diff = target - nums[i]\n",
    "            if nums[i] not in bucket:\n",
    "                bucket[diff] = i\n",
    "            else:\n",
    "                return [nums[i],diff]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        dict={}\n",
    "        for i in range(0,len(nums)):\n",
    "            if nums[i] not in dict:\n",
    "                dict[target-nums[i]]=i\n",
    "            else:\n",
    "                res=[nums[i]]\n",
    "                res.append(target-nums[i])\n",
    "                return res\n",
    "        return []\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        d = set()\n",
    "        for num in nums:\n",
    "            if target-num in d:\n",
    "                return [num, target-num]\n",
    "            d.add(num)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        _set = set()\n",
    "        for item in nums:\n",
    "            if target - item in _set:\n",
    "                return [item, target-item]\n",
    "            else:\n",
    "                _set.add(item)\n",
    "        return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        d = {}\n",
    "        for num in nums:\n",
    "            if not d.get(target-num, None):\n",
    "                d[num] = True\n",
    "            else:\n",
    "                return [num, target-num]\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        dic = {}\n",
    "        for num in nums:\n",
    "            if num in dic.keys():\n",
    "                return [num, dic.get(num)]\n",
    "            else:\n",
    "                dic[target-num] = num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        # 方法2：\n",
    "        a = {}\n",
    "        for i in nums:\n",
    "            if target % 2 == 0:\n",
    "                if i == target // 2:\n",
    "                    continue\n",
    "            a[i] = target - i\n",
    "            if target - i in a.keys():\n",
    "                return i, target-i\n",
    "        return -1\n",
    "            \n",
    "\n",
    "        # 应使用二分查找？\n",
    "        count1 = 0\n",
    "        \n",
    "        while count1 < len(nums) - 1:\n",
    "            if nums[count1] >= target:\n",
    "                break\n",
    "            count1 += 1\n",
    "\n",
    "        while count1 > 0:\n",
    "            count2 = count1 - 1\n",
    "            while count2 >= 0:\n",
    "                if nums[count1]+nums[count2] == target:\n",
    "                    return nums[count2],nums[count1]\n",
    "                count2 -= 1\n",
    "            count1 -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        sl = SortedList()\n",
    "        for each in nums:\n",
    "            sl.add(each)\n",
    "        length = len(sl)\n",
    "        for i in range(length):\n",
    "            j = sl.bisect(target - sl[i])\n",
    "            if j==0:\n",
    "                continue\n",
    "            if sl[j-1] == target - sl[i]:\n",
    "                return [sl[i], sl[j-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        dic = dict()\n",
    "        for i in nums:\n",
    "            if target - i in dic:\n",
    "                return [i,target-i]\n",
    "            if i not in dic:\n",
    "                dic[i] = i\n",
    "        return [0,0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "\n",
    "        a={}\n",
    "        for i in nums:\n",
    "            if target-i in a:\n",
    "                return [i,target-i]\n",
    "            a[i]=0\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        cnt_dict = {}\n",
    "        for i in range(len(nums)):\n",
    "            if target-nums[i] in cnt_dict:\n",
    "                return [nums[i], target-nums[i]]\n",
    "            cnt_dict[nums[i]] = 1\n",
    "        return [0,0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        mp = collections.Counter()\n",
    "        for n in nums:\n",
    "            if mp[target-n] != 0:\n",
    "                return n,target-n\n",
    "            mp[n] += 1\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        dic = {}\n",
    "        ele = nums.pop()\n",
    "        while ele not in dic:\n",
    "            dic[target-ele] = ele\n",
    "            ele = nums.pop()\n",
    "        return [ele, dic[ele]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        left, right = 0, len(nums) -1 \n",
    "        d = set()\n",
    "        while(left<right):\n",
    "            if(target - nums[left] not in d):\n",
    "                d.add(nums[left])\n",
    "                left += 1\n",
    "            else:\n",
    "                return [nums[left], target - nums[left]]\n",
    "            if(target - nums[right] not in d):\n",
    "                d.add(nums[right])\n",
    "                right -= 1\n",
    "            else:\n",
    "                return [nums[right], target - nums[right]]\n",
    "\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        s = set()\n",
    "        for x in nums:\n",
    "            if target - x in s:\n",
    "                return [target-x,x]\n",
    "            s.add(x)\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        hashset = set()\n",
    "        for num in nums:\n",
    "            if target-num in hashset:\n",
    "                return [num,target-num]\n",
    "            if num not in hashset:\n",
    "                hashset.add(num)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        hashset = set()\n",
    "        for num in nums:\n",
    "            if target-num in hashset:\n",
    "                return [num,target-num]\n",
    "            if num not in hashset:\n",
    "                hashset.add(num)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        a = set(nums)\n",
    "        for i in a:\n",
    "            if target - i in a:\n",
    "                return [i,target-i]\n",
    "        return None\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        s = set(nums)\n",
    "        for i in nums:\n",
    "            if target - i in s:\n",
    "                return[i,target - i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        nums = set(nums)\n",
    "        for num in nums:\n",
    "            if target-num in nums:\n",
    "                return [num, target-num]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        nums = set(nums)\n",
    "        for i in nums:\n",
    "            if target - i in nums:\n",
    "                return [i, target-i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        sum_dict = {}\n",
    "        for i in nums:\n",
    "            if i in sum_dict:\n",
    "                return [i, sum_dict[i]]\n",
    "            else:\n",
    "                sum_dict[target-i] = i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        ha = dict()\n",
    "        for num in nums:\n",
    "            if num in ha:\n",
    "                return [num, ha[num]]\n",
    "            ha[target-num] = num\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        # 使用dict存储nums[i]所在的索引\n",
    "        dic={}\n",
    "\n",
    "        for i,x in enumerate(nums):\n",
    "            y=target-x\n",
    "            if y in dic:\n",
    "                return x, y\n",
    "            \n",
    "            dic[x]=i\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        n_dic = {}\n",
    "        for i in nums:\n",
    "            if i in n_dic.keys():\n",
    "                return [i, n_dic[i]]\n",
    "            else:\n",
    "                n_dic[target-i] = i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        d = {}\n",
    "        for a in price:\n",
    "            b = target - a\n",
    "            if b in d:\n",
    "                return [a, b]\n",
    "            d[a] = a\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        index_map = {}\n",
    "        \n",
    "        for i, num in enumerate(price):\n",
    "            # 计算目标值与当前价格的差值\n",
    "            complement = target - num\n",
    "            \n",
    "            # 检查差值是否存在于字典中，如果存在，返回结果\n",
    "            if complement in index_map:\n",
    "                return [complement, price[i]]\n",
    "            \n",
    "            # 否则将当前价格与其索引添加到字典中\n",
    "            index_map[num] = i\n",
    "\n",
    "        # 如果没有找到合适的元素，返回空列表\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "\n",
    "\n",
    "        hashMap = {}\n",
    "        for i in range(len(price)):\n",
    "            if price[i] in hashMap:\n",
    "                return [hashMap[price[i]], price[i]]\n",
    "            else:\n",
    "                hashMap[target - price[i]] = price[i]\n",
    "      \n",
    "        return []\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        mapping = dict()\n",
    "        for i in range(len(price)):\n",
    "            sencond = target - price[i]\n",
    "            if sencond in mapping:\n",
    "                return [price[i], sencond]\n",
    "            else:\n",
    "                mapping[price[i]] = i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        dic = {}\n",
    "        for num in price:\n",
    "            if num not in dic:\n",
    "                dic[target - num] = num\n",
    "            elif num in dic:\n",
    "                return [num, dic[num]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        partner = {}\n",
    "        for i in price:\n",
    "            if i in partner:\n",
    "                return [i, partner[i]]\n",
    "            else:\n",
    "                partner[target - i] = i\n",
    "        return []\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        price_set = set()\n",
    "        for i in price:\n",
    "            if target - i in price_set:\n",
    "                return [i,target-i]\n",
    "            price_set.add(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        price_set = set()\n",
    "        for i in price:\n",
    "            if target - i in price_set:\n",
    "                return [i,target-i]\n",
    "            price_set.add(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        nums=set(nums)\n",
    "        for i in nums:\n",
    "            if (target-i) in nums:\n",
    "                return [i,target-i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if nums[mid] == target:\n",
    "                left = mid + 1\n",
    "                break\n",
    "            elif nums[mid] > target:\n",
    "                right = mid - 1\n",
    "            elif nums[mid] < target:\n",
    "                left = mid + 1\n",
    "        nums = nums[:left]\n",
    "        memo = {}\n",
    "        for num in nums:\n",
    "            if target - num in memo:\n",
    "                return [num, target-num]\n",
    "            if num not in memo:\n",
    "                memo[num] = 1\n",
    "        return [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        # 用一个hashset保存数组中的数字\n",
    "        s = set(nums)\n",
    "        for e in nums:\n",
    "            if target - e in s:\n",
    "                return [e, target-e]\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        a = set(nums)\n",
    "        for x in nums:\n",
    "            if target-x in a:\n",
    "                return [x,target-x]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        s=set()\n",
    "        for i,el in enumerate(nums):\n",
    "            if el in s:\n",
    "                return [el,target-el]\n",
    "            else:\n",
    "                s.add(target-el)\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        hashtable = set()\n",
    "        for n in nums:\n",
    "            if target - n in hashtable: return [n, target-n]\n",
    "            hashtable.add(n)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        ha = set()\n",
    "        for num in nums:\n",
    "            if target-num in ha:\n",
    "                return [num, target-num]\n",
    "            ha.add(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        \n",
    "        hashset = set()\n",
    "        for n in nums:\n",
    "            if target - n in hashset: return (n, target-n)\n",
    "            hashset.add(n)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        res = set()\n",
    "        \n",
    "        for i,num in enumerate(nums):\n",
    "            if target-num in res:\n",
    "                return [target-num,num]\n",
    "            res.add(num)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        sets = set()\n",
    "        for i in nums:\n",
    "            if target - i in sets:\n",
    "                return [i, target - i]\n",
    "            else:\n",
    "                sets.add(i)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        # write code here\n",
    "        dic = {target - numbers[0]: 0}\n",
    "        for i in range(1, len(numbers)):\n",
    "            tar = dic.get(numbers[i], None)\n",
    "            if tar is None:\n",
    "                dic[target - numbers[i]] = i\n",
    "            else:\n",
    "                return [numbers[tar], numbers[i]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        price_set = set()\n",
    "        for i in price:\n",
    "            if target - i in price_set:\n",
    "                return [i,target-i]\n",
    "            if i not in price_set:\n",
    "                price_set.add(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        uset=set()\n",
    "        for p in price:\n",
    "            if target-p in uset:\n",
    "                return [target-p,p]\n",
    "            uset.add(p)\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        # my_map = set()\n",
    "        # for i,n in enumerate(nums):\n",
    "        #     if target - n in my_map:\n",
    "        #         return [target-n,n]\n",
    "        #     my_map.add(target-n)\n",
    "        seen = set()             \n",
    "        for i, num in enumerate(nums):\n",
    "            complement = target - num\n",
    "            if complement in seen:\n",
    "                return [complement, num]\n",
    "            seen.add(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "\n",
    "\n",
    "        diction = set()\n",
    "        for i in nums:    \n",
    "            if i > target:\n",
    "                break\n",
    "            if target - i in diction:\n",
    "                return [i, target-i]\n",
    "            diction.add(i)\n",
    "            \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        s = set(nums)\n",
    "        for i in nums:\n",
    "            if target - i in s:\n",
    "                return [i, target-i]\n",
    "                break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        a = set(nums)\n",
    "        for i in a:\n",
    "            if target - i in a:\n",
    "                return [i,target-i]\n",
    "        return None\n",
    "\n",
    "# 作者：listenli\n",
    "# 链接：https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/solution/set-python3-by-listenli-t5nx/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        # l,r = 0, len(nums)-1\n",
    "        # while l<r:\n",
    "        #     if nums[l] + nums[r] == target:\n",
    "        #         return [nums[l],nums[r]]\n",
    "        #     if nums[l] + nums[r] > target:\n",
    "        #         r -= 1\n",
    "        #     else:\n",
    "        #         l += 1\n",
    "        # return []\n",
    "\n",
    "        hashmap = set()\n",
    "        hashmap.add(nums[0])\n",
    "        for num in nums[1:]:\n",
    "            if target - num in hashmap:\n",
    "                return [num, target-num]\n",
    "            else:\n",
    "                hashmap.add(num)\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        hash_table = dict()\n",
    "        for num in nums:\n",
    "            if num in hash_table:\n",
    "                res = [num, hash_table[num]]\n",
    "            else:\n",
    "                hash_table[target - num] = num\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        i, j = 0, len(nums)-1\n",
    "        while i<=j:\n",
    "            m = (i+j)//2\n",
    "            if target > nums[m]:\n",
    "                i = m + 1\n",
    "            elif target < nums[m]:\n",
    "                j = m - 1\n",
    "            else:\n",
    "                i = m\n",
    "                break\n",
    "        occ = set()\n",
    "        for idx, num in enumerate(nums[:i+1]):\n",
    "            if target - num in occ:\n",
    "               return [num, target-num]\n",
    "            occ.add(num)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, price: List[int], target: int) -> List[int]:\n",
    "        visited = set()\n",
    "        for num in price:\n",
    "            if target - num in visited:\n",
    "                return [target - num, num]\n",
    "            visited.add(num)\n",
    "        return []\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
